// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include <unordered_map>
#include "commoncppproblem508.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=508 lang=cpp
 *
 * [508] 出现次数最多的子树元素和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int FindTreeSum(unordered_map<int,int> &sum,TreeNode* root)
    {
        if(root == NULL)
            return 0;
        int temp = root->val;
  
        int left = FindTreeSum(sum,root->left);
        int right = FindTreeSum(sum,root->right);
    
        temp += left;
        temp += right;

        sum[temp]++;

        return temp;
    }


    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int,int> sum;
        vector<int> res;
        FindTreeSum(sum,root);
        int maxfre = 0;
        for(auto it = sum.begin();it!=sum.end();it++)
        {
            if(it->second > maxfre)
            {
                maxfre = it->second;
                res.clear();
                res.push_back(it->first);
            }
            else if(it->second == maxfre)
            {
                res.push_back(it->first);
            }
        }
        return res;
    }
};
// @lc code=end

